/**
 * 
 */
package leetCode;

import java.util.Stack;

/**
 * @author zhong
 *
 */
public class ScoreofParentheses {

	public int scoreOfParentheses(String S) {
		int n = S.length();
		Stack<Integer> stack = new Stack<>();
		Stack<Integer> val = new Stack<>();
		Stack<Integer> left = new Stack<>();
		for (int i = 0; i < n; i++) {
			if (S.charAt(i) == '(') {
				stack.push(i);
			} else {
				int op = stack.pop();
				if (i == op + 1) {
					val.push(1);
					left.push(op);
				} else {
					int sum = 0;
					int firstPos = -1;
					while (!left.isEmpty() && left.peek() > op) {
						sum += val.pop();
						if (firstPos == -1) {
							firstPos = left.pop();
						} else {
							left.pop();
						}

					}
					if (sum != 0) {
						sum *= 2;
						val.push(sum);
						left.push(firstPos);
					}
				}
			}
		}
		int res = 0;
		while (!val.isEmpty()) {
			res += val.pop();
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "(()(()))";
		System.out.println(new ScoreofParentheses().scoreOfParentheses(S));
	}

}
